For the existing steganography, it is hard to extract secret information without original cover-image and easy to be detected by steganalysts when the hiding capacity is high. To solve this problem, a new scheme of steganography based on fractal graph was proposed. In this scheme, firstly, Black-and-White Fractal Graph (BWFG) was created by utilizing affine transformation and fractal iterated function system. Then the BWFG was transformed to Black-and-White Pixel Image (BWPI) based on the idea of coordinate transformation. At last, the BWPI was divided into several non-overlapping blocks and the positions of black and white pixels in each block were altered to hide the secret information, generating stego-image. The receiver could create the cover-image by utilizing the parameters of affine transformation and times of iteration, and extract secret information by comparing the difference of pixels in corresponding blocks. Theoretical analysis and simulation experiments show that, compared with the information hiding algorithm in frequency domain, the proposed scheme has good imperceptibility and high hiding capacity, and can resist steganalysis based on image features and transform domain coefficient change.